class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        length = len(prices)
        for j in range(1, length):
            prices[length - j] -= prices[length - j - 1]
        prices[0] = 0
        DP1 = [0] * length
        DP2 = [0] * length
        DP3 = [0] * length
        DP4 = [0] * length
        for i in range(length):
            if i == 0:
                DP1[i] = 0
                DP2[i] = 0
                DP3[i] = 0
                DP4[i] = 0
            else:
                DP1[i] = max(DP1[i - 1] + prices[i], prices[i])
                DP2[i] = max(DP2[i - 1], DP1[i - 1])
                if i == 1:
                    DP3[i] = 0
                    DP4[i] = 0
                else:
                    DP3[i] = max(DP2[i - 1] + prices[i], DP3[i - 1] + prices[i])
                    if i == 2:
                        DP4[i] = 0
                    else:
                        DP4[i] = max(DP4[i - 1], DP3[i - 1])
        return max(DP1[-1], DP2[-1], DP3[-1], DP4[-1])


data = Solution()
prices = [1, 3, 1, 5, 8, 4, 2, 7]
print(data.maxProfit(prices))
